package com.cty._01_Base._03_01_DuplicationInArray;

/**
 * @Auther: cty
 * @Date: 2020/6/8 10:31
 * @Description: 面试题3：数组中重复的数字
 * 题目一：找出数组中重复的数字
 *      在一个长度为 n 的数组里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，
 *      也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果出入长度为 7 的数组 {2,3,1,0,2,5,3},
 *      那么对应的输出是重复的数字 2 或者 3。
 *
 * 输入 & 测试用例分析：
 *      ① 空指针
 *      ② 长度为0
 *      ③ 输入不在指定范围
 *      ④ 边界值有效性
 *      ⑤ 多种情况
 * @version: 1.0
 */
public class DuplicationInArray {
    /**
     * 找出数组中重复的数字
     * 要求：
     *      可以修改数组
     *      找出数组中任意一个重复的数组
     * 效率：
     *      时间  O(N)
     *      空间  O(1)
     * @param array  数组引用
     * @param length  数组中元素个数
     * @return
     */
    public static int getDuplicate(int[] array, int length)
    {
        // 空指针或数组为空
        if(array==null || length==0){
            return -1;
        }

        // 数组中包含不在0~n-1范围内的数字
        for(int i=0; i<length; i++)
            if(array[i]<0 || array[i]>=length)
                return -2;

        // 从数组中获取一个重复的数字
        for(int i=0; i<length; i++)
        {
            while(array[i] != i){
                if(array[array[i]] == array[i])
                    return array[i];
                else{
                    int temp = array[i];
                    array[i] = array[temp];
                    array[temp] = temp;
                }  // end else
            }  // end if
        }  // end for
        return -3;  // 数组中不包含重复数字
    }  // end method getDuplicate

}  // end class
